package com.itheima.algorithm.hashtable;

import java.util.Arrays;
import java.util.Collections;
import java.util.Map;
import java.util.stream.Collectors;

public class HashTable {
    //节点类
    static class Entry{
        int hash;//哈希码
        Object key;//键
        Object value;//值
        Entry next;

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    Entry[] table=new Entry[16];
    int size=0;//元素个数
    float loadFactor=0.75f;//负载因子 12 阈值
    int threshold= (int) (loadFactor*table.length);//阈值

    /*
    求模运算可以替换为与运算
    hash%数组长度==hash & (数组长度-1)
     */

    //根据hash码获取value
    Object get(int hash,Object key){
        int idx=hash&(table.length-1);//找到在表中的位置
        if(table[idx]==null){
            return null;//这个值根本没有
        }
        Entry p=table[idx];//从每个索引的链表头开始查找
        while(p!=null){
            if(p.key.equals(key)){
                return p.value;
            }
            p=p.next;
        }
        return null;
    }

    //向哈希表新增元素
    void put(int hash,Object key,Object value){
        int idx=hash&(table.length-1);
        if(table[idx]==null){
            //1.idx处table有一个空位，直接插入即可
            table[idx]=new Entry(hash,key,value);
            size++;
        }else{
            //2.idx处没有空位，从链表头开始遍历链表，有重复的key就更新。否则新增
            Entry p=table[idx];
            while(true){
                if(p.key.equals(key)){
                    p.value=value;//更新
                    return ;
                }
                if(p.next==null){
                    break;//走到最后一个元素都找不到，可以退出，在哈希表对应节点处链表插入
                }
                p=p.next;
            }
            p.next=new Entry(hash,key,value);//新增
            size++;
            if(size>threshold){
                resize();
            }
        }
    }

    private void resize(){
        Entry[] newTable=new Entry[table.length<<1];
        for(int i=0;i< table.length;i++){
            //拿到每个链表头
            Entry p=table[i];
            if(p!=null){
                //拆分链表
                /*
                拆分规则：
                最多拆成两组
                hash & table.length==0为一组；
                hash & table.length！=0为一组；
                 */
                  Entry a=null;
                  Entry b=null;
                  Entry aHead=null;
                  Entry bHead=null;
                  while(p!=null){
                      if((p.hash& table.length)==0){
                          //分配到a
                          if(a!=null){
                              a.next=p;
                          }else{
                              aHead=p;
                          }
                          a=p;
                      }else{
                          //分配到b
                          if(b!=null){
                              b.next=p;
                          }else{
                              bHead=p;
                          }
                          b=p;
                      }
                      p=p.next;
                  }

                  if(a!=null){
                      a.next=null;
                      newTable[i]=aHead;
                  }
                  if(b!=null){
                      b.next=null;
                      newTable[i+ table.length]=bHead;
                  }
            }
        }
        table=newTable;
        threshold=(int)(loadFactor* table.length);
    }

    //根据哈希码进行删除，返回删除的value
    Object remove(int hash,Object key){
        int idx=hash&(table.length-1);
        if(table[idx]==null){
            return null;
        }
        Entry p=table[idx];
        Entry prev=null;
        while(p!=null){
            if(p.key.equals(key)){
                //找到了删除；
                if(prev==null){
                    table[idx]=p.next;
                }else{
                    prev.next=p.next;
                }
                size--;
                return p.value;
            }
            prev=p;
            p=p.next;
        }
        return null;
    }

    public Object get(Object key){
        int hash=hash(key);
        return get(hash,key);
    }

    public void put(Object key,Object value){
        int hash=hash(key);
        put(hash,key,value);
    }

    public Object remove(Object key){
        int hash=hash(key);
        return remove(hash,key);
    }

    public void print(){
        int[] sums=new int[table.length];
        for(int i=0;i<table.length;i++){
            Entry p=table[i];
            while(p!=null){
                sums[i]++;
                p=p.next;
            }
        }
        //System.out.println(Arrays.toString(sums));
        Map<Integer,Long> collect=Arrays.stream(sums).boxed().collect(Collectors.groupingBy(e -> e,Collectors.counting()));
        System.out.println(collect);
    }

    private static int hash(Object key){
        //解决String重写hashCode方法的问题
        if(key.getClass().getTypeName().equals(String.class)){
            int hash=0;
            String s1=(String) key;
            for(int i=0;i<s1.length();i++){
                char c=s1.charAt(i);
                hash=(hash<<5)-hash+c;
            }
            return hash;
        }
        int hash=key.hashCode();
        return hash^(hash>>>16);
    }

    public static void main(String[] args) {
        HashTable hashTable=new HashTable();
        for(int i=0;i<20000;i++){
            Object obj=new Object();
            hashTable.put(obj,obj);
        }
        hashTable.print();
    }
}
